/*
*
给你一个下标从 0 开始的 m x n 整数矩阵 grid 和一个整数 k 。你从起点 (0, 0) 出发，每一步只能往 下 或者往 右 ，你想要到达终点 (m - 1, n - 1) 。

请你返回路径和能被 k 整除的路径数目，由于答案可能很大，返回答案对 109 + 7 取余 的结果。

示例 1：

输入：grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
输出：2
解释：有两条路径满足路径上元素的和能被 k 整除。
第一条路径为上图中用红色标注的路径，和为 5 + 2 + 4 + 5 + 2 = 18 ，能被 3 整除。
第二条路径为上图中用蓝色标注的路径，和为 5 + 3 + 0 + 5 + 2 = 15 ，能被 3 整除。
示例 2：

输入：grid = [[0,0]], k = 5
输出：1
解释：红色标注的路径和为 0 + 0 = 0 ，能被 5 整除。
示例 3：

输入：grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
输出：10
解释：每个数字都能被 1 整除，所以每一条路径的和都能被 k 整除。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 5 * 104
1 <= m * n <= 5 * 104
0 <= grid[i][j] <= 100
1 <= k <= 50

  - @author ala
  - @date 2024-09-20 13:25
*/
package main

import "fmt"

func main() {
	//grid := [][]int{{5, 2, 4}, {3, 0, 5}, {0, 7, 2}}
	//k := 3

	//grid := [][]int{{0, 0}}
	//k := 5

	grid := [][]int{{7, 3, 4, 9}, {2, 3, 6, 2}, {2, 3, 7, 0}}
	k := 1

	fmt.Println(numberOfPaths(grid, k))
}

/**
 *	1）dp[i][j][k]表示：(i,j)位路径和 % k的路径数
 *	2）dp[i][j][(_k + grid[i][j]) % k] = sum(dp[i-1][j][_k])
 *											+
 *					 					 sum(dp[i][j-1][_k])
 *	3）dp[0][0][grid[0][0] % k] = 1
 *	4）dp[M - 1][N - 1]即为答案
 */
func numberOfPaths(grid [][]int, k int) int {
	M, N := len(grid), len(grid[0])

	dp := make([][][]int, M)
	for i := range dp {
		dp[i] = make([][]int, N)
		for j := range dp[i] {
			dp[i][j] = make([]int, k)
		}
	}

	for i := range dp {
		for j := range dp[i] {
			v := grid[i][j]
			if i == 0 && j == 0 {
				dp[i][j][v%k] = 1
				continue
			}

			for _k := 0; _k < k; _k++ {
				__k := (_k + v) % k
				if i > 0 && dp[i-1][j][_k] > 0 {
					dp[i][j][__k] = (dp[i][j][__k] + dp[i-1][j][_k]) % MOD
				}
				if j > 0 && dp[i][j-1][_k] > 0 {
					dp[i][j][__k] = (dp[i][j][__k] + dp[i][j-1][_k]) % MOD
				}
			}
		}
	}

	return dp[M-1][N-1][0]
}

var MOD int = 1e9 + 7
